{\rtf1\ansi\ansicpg1252\deff0\deflang1033{\fonttbl{\f0\fswiss\fcharset0 Arial;}} {\*\generator Msftedit 5.41.15.1507;}\viewkind4\uc1\pard\f0\fs20 Radix Sort\par ========\par \par Consider a list L of N integers of at most D digits\par \tab 1. Construct 10 bins, labeled 0, 1, ... 9\par \tab 2. For i = D down to 1\par \tab\tab Append each element of L to the bin corresponding to its ith digit\par \tab\tab (i.e., start with least significant)\par \tab\tab Read the values in the bins back into L\par \tab\tab (i.e., from 0 to 9, from first to last)\par \par Class exercise\par \tab Apply the above procedure to the following lists\par \tab\tab L1 = 36 9 0 25 1 49 64 16 81 4\par \tab\tab L2 = 456 342 89 678 999 12 521 575 201 722 866 491\par \par \tab (a) Demo.java\par \tab\tab Implementation for integers\par \par \tab (b) http://www.cs.auckland.ac.nz/software/AlgAnim/radixsort.html\par \tab\tab See "Run the Animatiom" at the bottom of the page\par \tab\tab Graphical demo\par \par How efficient is radix sort compared to the other sorting techniques we have\par studied?\par \par \tab (c) http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html\par \tab\tab Run the demo on a few\par \tab\tab Check Heap Sort in passing\par \par What is the bigOh of Radix Sort?\par \tab We first generalize the above procedure\par \tab Then, we analyze its complexity\par \par The above procedure for integers can be generalized as follows.\par \tab Assume that the items in L have keys\par \tab Assume that the key contains K fields\par \tab Assume that each field Fi has Si discrete possible values\par \tab Then:\par \tab\tab 1. For Fi = Fk down to F1\par \tab\tab\tab Construct Si bins\par \tab\tab\tab Append each element of L to the bin corresponding to the \par \tab\tab\tab value of the ith field of its key\par \tab\tab\tab Concatenate the bins together to form a new L\par \par Let us consider each step of the above algorithm\par \par \tab For Fi = Fk down to F1\tab\tab - this will execute K times\par \tab\tab Construct Si bins\tab - this is O(Si)\par \tab\tab Append ...\tab\tab - this is O(N)\par \tab\tab Concatenate ...\tab\tab - this is O(Si)\par \par Hence, we have:\par \tab Sum(i=1,K) O(Si + N + Si)\tab = Sum(i=1,K) O(N + Si)\par \tab\tab\tab\tab\tab = O(KN + Sum(i=1,K) Si)\par \tab\tab\tab\tab\tab = O(N + Sum(i=1,K) Si)\par \par Now, if the keys are integers in [0, B^K-1] for some constant K, then the keys can be\par viewed as K-digit base-B integers. It follows that Si = B for all i and the time complexity\par becomes:\par \tab O(N + Sum(i=1,K) Si)\tab = O(N + Sum(i=1,K) B)\par \tab\tab\tab\tab = O(N + KB)\par \tab\tab\tab\tab = O(N)\par \par This result assumes that K is constant! If K is allowed to increase with N, things change.\par For example, it takes logN binary digits to represent an integer less than N. If the key \par length is allowed to increase with N so that K = logN, then the complexity becomes:\par \tab Sum(i=1,K) O(N+Si)\tab = O(KN + Sum(i=1,K) Si)\par \tab\tab\tab\tab = O(NlogN + Sum(i=1,logN) 2)\par \tab\tab\tab\tab = O(NlogN + 2logN)\par \tab\tab\tab\tab = O(NlogN)\par \par Note that Radix Sort does not perform any comparison at all, which explains why we may\par do better than the most efficient O(NlogN) of comparison-based techniques. With appropriate, \par constant-length keys, we may sort in O(N). And in the worst case, we are no worse than\par the best comparison-based techniques such as quickSort!\par }